lib/Mi manual de algoritmos/version_maraton_suramericana_2008/src/geometria/is_inside_convex_polygon.cpp

   1 /*
   2   Returns true if point a is inside convex polygon p.
   3   Note that if point a lies on the border of p it
   4   is considered outside.
   5
   6   We assume p is convex! The result is useless if p
   7   is concave.
   8  */
   9 bool insideConvexPolygon(const vector<point> &p, const point &a){
  10   int mask = 0;
  11   int n = p.size();
  12   for (int i=0; i<n; ++i){
  13     int j = (i+1)%n;
  14     double z = turn(p[i], p[j], a);
  15     if (z < 0.0){
  16       mask |= 1;
  17     }else if (z > 0.0){
  18       mask |= 2;
  19     }else if (z == 0.0) return false;
  20     if (mask == 3) return false;
  21   }
  22   return mask != 0;
  23
  24 }